今日題目

題目連結：605. Can Place Flowers
題目主題：Array, Greedy

昨天介紹了 Greedy 的基本概念，今天會在練習一題以 Greedy 當主題的題目，建議還沒看過 Greedy 可以先回 Day 23：1974. Minimum Time to Type Word Using Special Typewriter 看看簡單說說 Greedy。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給你一個 flowerbed 花圃，我們要在這裡面種植，這個 flowerbed 中 0 代表沒有種植、1 代表有種植，另外會給一個 n 代表要種植的數量，目的是確認 flowerbed 中還能不能再種植 n 朵花，若可以回傳 True，不行則回 False。

約束：

• 1 <= flowerbed.length <= 2 * 10的4次方。
• flowerbed[i] 不是 0 就是 1。
• flowerbed 中花跟花之間不會靠在一起，中間一定會有一個空。
• 0 <= n <= flowerbed.length。

範例1

輸入: flowerbed = [1,0,0,0,1], n = 1
輸出: true
解說: flowerbed中間還可以再插一朵花，n 剛好是 1，因此這個範例回 true。

範例2

輸入: flowerbed = [1,0,0,0,1], n = 2
輸出: false
解說: flowerbed中間只能再插一朵花，因為花不能靠在一起，n 還有兩朵花，因此這個範例回 false。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 寫一個遞迴方法，傳入目標的種花數量、花圃、目前位置，最終回傳是否能把花全部種完，會檢查以下項目：
   • 若種花數量已經到 0 代表成功把花都種完了。
   • 若目前的位置已經超出花圃範圍，代表失敗，沒有把花種完。
   • 每一步會有三種可能性：
     • 若現在位置有花 前進兩步。
     • 若現在位置+1有花 前進三步。
     • 若現在位置沒花 種1朵花 前進兩步。
2. 呼叫這個遞迴方法，最後回傳是否能成功把花種完的結果。

圖解過程

範例：flowerbed = [0, 0, 1, 0, 0, 1, 0, 0], n = 2

上圖這個例子中，可以先看 step1 ~ step2，從 step1 開始走，當目前位置沒有種花時，會將花種下去，並且往前兩步，也因目前點種下花，以條件來說下一個點必為空，所以可以看到 step2 的 count 已經 -1 了，並且前進了兩步。

step3 因為當下的位置已經有花了，100 中 1 的旁邊不能種花，也是直接往前走兩步。step4 比較特別，雖然當下的位置沒有花，但是因為下一個位置有花不能在這邊種花，所以直接前進了三步，原因是 0100 中 1 的旁邊都不能種花了，所以可以確定直接往前三步沒問題。

step4 前進了三步走到最後的位置後，因為當下的位置是 0 ，所以在這邊把最後一朵花種下去，最後 step5 的 count 已經是 0 了，最後這個範例是成功可以把花種完的。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def planting(self, count, flowerbed, index = 0):
        # 若把花全部種完回 True
        if count == 0: return True
        # 若花圃都走過一次還沒種完回 False
        if index >= len(flowerbed): return False
        
        # 若現在位置有花 前進兩步
        if flowerbed[index] == 1:
            return self.planting(count, flowerbed, index+2)
        # 若現在位置+1有花 前進三步
        if (index+1 < len(flowerbed)) and flowerbed[index+1] == 1:
            return self.planting(count, flowerbed, index+3)
        # 若現在位置沒花 種1朵花 前進兩步
        if flowerbed[index] == 0:
            flowerbed[index] = 1
            return self.planting(count - 1, flowerbed, index+2)
    
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        return self.planting(n, flowerbed)

希望您今天能瞭解到...

1. 605. Can Place Flowers的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：53. Maximum Subarray